//面试题 08.06. 汉诺塔问题
/*在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。*/

class Solution {
public:
    void finish_hanota(vector<int>& x, vector<int>& y, vector<int>& z, int n) {
        if (n == 1) {
            z.push_back(x.back());
            x.pop_back();
            return;
        }
        finish_hanota(x, z, y, n - 1);
        z.push_back(x.back());
        x.pop_back();
        finish_hanota(y, x, z, n - 1);
    }
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        if (A.size())
            finish_hanota(A, B, C, A.size());
    }
};

//合并两个有序链表
/*将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void dfs(ListNode* n1, ListNode* n2, ListNode* head) {
        if (n1 && n2) {
            if (n1->val < n2->val) {
                head->next = n1;
                dfs(n1->next, n2, head->next);
            } else {
                head->next = n2;
                dfs(n1, n2->next, head->next);
            }
        } else if (n1) {
            head->next = n1;
            dfs(n1->next, n2, head->next);
        } else if (n2) {
            head->next = n2;
            dfs(n1, n2->next, head->next);
        }
        return;
    }
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* new_list = new ListNode;
        dfs(list1, list2, new_list);
        return new_list->next;
    }
};
//Pow(x, n)
/*实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。*/
class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0)
            return 1;
        if (n > 0) {
            if (n == 1)
                return x;
            double _temp = myPow(x, n / 2);
            if (n % 2) {
                return _temp * _temp * x;
            } else {
                return _temp * _temp;
            }
        } else {
            if (n == -1)
                return 1 / x;
            double _temp = myPow(x, n / 2);
            if (n % 2) {
                return _temp * _temp * (1 / x);
            } else {
                return _temp * _temp;
            }
        }
    }
};